//交易逆序对的总数
//测试链接 https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
public class ReversePairs {
    int[] help;
    public int reversePairs(int[] record) {
        help = new int[record.length];

        return merge(record, 0 , record.length-1);
    }

    public int merge(int[] nums, int left, int right){
        if(left >= right) return 0;

        int mid = left + (right - left)/2; //找到中点

        int ans1 = merge(nums,left,mid);     //左半部分个数
        int ans2 = merge(nums,mid+1, right); //右半部分个数
        //排序左右两边

        int cur1 = left, cur2 = mid+1, i = left;
        int ret = 0; //一左一右的个个数
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){
                help[i++] = nums[cur1];
                cur1++;
            }else{
                ret += mid - cur1 + 1;
                help[i++] = nums[cur2];
                cur2++;
            }
        }
        //处理剩余情况
        while(cur1 <= mid)  help[i++] = nums[cur1++];
        while(cur2 <= right)  help[i++] = nums[cur2++];

        //将排好序的数组重新刷回原数组
        for(int n = left; n <= right; n++){
            nums[n] = help[n];
        }
        return ret+ans1+ans2;
    }
}
